676. Implement Magic Dictionary

题目 676. Implement Magic Dictionary

思路分析

长度最大100 且最多询问100次 意味着可以暴力去解

对于每个seach的词 遍历一遍字典 看长度是否相等 如果相等 再看不一样的字符有几个 如果只有1个就true

如果数据量大的话 就不能使用暴力算法

可以使用前缀树（trie树）

先在树里进行匹配 如果有一个字符不一样 先标记为已修改 如果再碰到一个不一样 就说明不行

代码实现

class MagicDictionary {

    private String[] dictionary;

    public MagicDictionary() {
    }
    
    public void buildDict(String[] dictionary) {
        this.dictionary = dictionary;
    }
    
    public boolean search(String searchWord) {
        for(String word : dictionary){
            if(word.length()!=searchWord.length()){
                continue;
            }
            int diffCount=0;
            for(int i=0;i<word.length();i++){
                if(word.charAt(i)!=searchWord.charAt(i)){
                    diffCount++;
                    if(diffCount>1){
                        break;
                    }
                }
            }
            if(diffCount == 1){
                return true;
            }
        }
        return false;
        
    }
}

/**
 * Your MagicDictionary object will be instantiated and called as such:
 * MagicDictionary obj = new MagicDictionary();
 * obj.buildDict(dictionary);
 * boolean param_2 = obj.search(searchWord);
 */

class MagicDictionary {

    final int N = 10010;
    
    int[][] son = new int[N][26];
    int[] cnt = new int[N];
    int idx = 0;

    public MagicDictionary() {
    }
    
    public void buildDict(String[] dictionary) {
        for(String s : dictionary){
            insert(s);
        }
    }

    void insert(String str){
        int p=0;
        for(int i=0;i<str.length();i++){
            int u=str.charAt(i)-'a';
            if(son[p][u]==0){
                son[p][u]=++idx;
            }   
            p=son[p][u];
        }
        cnt[p]++;
    }
    
    public boolean search(String searchWord) {
        return dfs(0,searchWord,0,false);
    }

    private boolean dfs(int p,String s,int i,boolean modified){
        if(i==s.length()){
            return cnt[p]>0 && modified;
        }

        int u=s.charAt(i)-'a';

        if(modified){
            if(son[p][u]!=0){
                return dfs(son[p][u],s,i+1,true);
            }
            return false;
        }

        if(son[p][u]!=0){
            if(dfs(son[p][u],s,i+1,false)){
                return true;
            }
        }

        for(int j=0;j<26;j++){
            if(j!=u && son[p][j]!=0){
                if(dfs(son[p][j],s,i+1,true)){
                    return true;
                }
            }
        }
        return false;
    }
}

/**
 * Your MagicDictionary object will be instantiated and called as such:
 * MagicDictionary obj = new MagicDictionary();
 * obj.buildDict(dictionary);
 * boolean param_2 = obj.search(searchWord);
 */

class MagicDictionary {

    final int N = 10010;
    
    int[][] son = new int[N][26];
    int[] cnt = new int[N];
    int idx = 0;

    public MagicDictionary() {
    }
    
    public void buildDict(String[] dictionary) {
        for(String s : dictionary){
            insert(s);
        }
    }

    void insert(String str){
        int p=0;
        for(int i=0;i<str.length();i++){
            int u=str.charAt(i)-'a';
            if(son[p][u]==0){
                son[p][u]=++idx;
            }   
            p=son[p][u];
        }
        cnt[p]++;
    }
    
    public boolean search(String searchWord) {
        return dfs(0,searchWord,0,false);
    }

    private boolean dfs(int p, String s, int i, boolean modified){
        if(i == s.length()){
            return cnt[p] > 0 && modified;
        }

        int u = s.charAt(i) - 'a';

        // 如果我们已经修改过字符了，剩下的必须完全匹配
        if (modified) {
            // 只有当前字符对应的路存在，才能往下走
            if (son[p][u] != 0) {
                return dfs(son[p][u], s, i + 1, true);
            }
            return false;
        } 
        
        // 还没修改过，遍历所有可能的子节点
        else {
            for (int j = 0; j < 26; j++) {
                // 只有子节点存在才有意义
                if (son[p][j] != 0) {
                    if (j == u) {
                        // 字符匹配：不做修改，状态保持 modified = false
                        if (dfs(son[p][j], s, i + 1, false)) {
                            return true;
                        }
                    } else {
                        // 字符不匹配：在这里修改！状态变为 modified = true
                        if (dfs(son[p][j], s, i + 1, true)) {
                            return true;
                        }
                    }
                }
            }
        }
        
        return false;
    }

}

/**
 * Your MagicDictionary object will be instantiated and called as such:
 * MagicDictionary obj = new MagicDictionary();
 * obj.buildDict(dictionary);
 * boolean param_2 = obj.search(searchWord);
 */

同类题型

视频讲解